CISC 3310 Final Exam Review Sheet

1. Virtual memory. Know what "virtual" means, what "virtual memory" means, and how virtual memory is implemented. Know the difference between demand paging and anticipatory paging. Know how demand paging works and the extra tables (page map table, frame map table) and fields (use bit, dirty bit, in-core bit) that are required. Know what a page fault is, what happens when a program page faults. Know how to calculate addresses under demand paging. Know the difference between global and local page replacement strategies. Know page replacement algorithms, including FIFO, LRU, and LRU approximations: clock, second chance. Know how to count page replacements using a reference string. Understand thrashing, level of multiprogramming, principle of locality, working set theory. Be able to calculate effective access time when using a cache.

2. Process coordination and synchronization. Understand the concept of "cooperating sequential processes," and what it means to say processes run "at the same time." Understand the critical section problem and various attempts to solve that problem. Know what Dekker's algorithm is (but you don't have to memorize it) and understand the ideas that are built into it. Know the criteria for a successful solution to the CS problem (simple, symmetric, provide mutual exclusion, prevent mutual lockout (allow progress), prevent starvation (guarantee bounded waiting)).

3. Semaphores and Classic Process Coordination Problems: Know about semaphores: implementation (actual and theoretical), know the various kinds of semaphores and how they are used. Know the classic process coordination problems: Producer-Consumer, Bounded-Buffer (simple and full solution), Dining Philosophers', Readers and Writers (you do not need to reproduce the code for the last). Be able to apply semaphores to simple tasks.

4. Deadlock. Know the 4 necessary conditions for deadlock, and the 3 methods of handling deadlock. Be able to read a resource allocation graph, including one that has multiple instances of a resource. Know the algorithms for deadlock prevention. Understand the principles of deadlock avoidance. Be able to use the Banker's Algorithm for a single resource to determine whether a system is in a safe state or not. Understand the relation between a safe state, an unsafe state, and deadlock. Understand the concept of a safe sequence. Understand deadlock detection and recovery methods, including termination, rollback, and selecting a victim.

5. Disk management. Know disk structure, latency time, seek time, access time. Know and be able to apply seek time optimization algorithms (FCFS, SSTF, SCAN, C-SCAN, LOOK, C-LOOK) to schedule a list of I/O requests. Know the shortcomings of various algorithms.

6. File allocation methods. Know the four allocation methods: contiguous, linked, linked with FAT, indexed. Know how each is set up, its advantages and disadvantages, and what each is good and bad for (sequential or direct access or both).

7. Files. Know directory structure, including paths and links (shortcuts), tree structure, AFT and its fields. Know how the OS represents and manipulates a shared files. Understand the purpose of a time stamp, a lock, and the KFT. Know how the KFT protects files. Understand how the AFT and KFT are used for file synchronization and protection.

8. Project: Know how your project works and how it interacts with SOS. Remember the problems you have encountered in writing and debugging the project. Know the code you wrote.